#ifndef AVLTREE_H_
#define AVLTREE_H_
#include"bstree.h"

template<typename K,typename V>
class avltree:public bstree<K,V>
{
public:
	typedef treenode<K, V>* pointer;
	static const int bf = 1;
	avltree() :bstree(){}
	avltree(K k, V v) :bstree(k, v){}
	
	void insert(K k, V v)
	{
		
		pointer temp = search(k);
		if (temp->key == k)
		{
			cout << "the key is exist" << endl;
			return;
		}

		pointer node = new treenode<K, V>(k, v);

		if (temp->key > k)
		{
			node->parent = temp;
			temp->lchild = node;
			temp->depthBelow();
			node->heightAbove();
		}
		else
		{
			node->parent = temp;
			temp->rchild = node;
			temp->depthBelow();
			node->heightAbove();
		}
		if (temp != nullptr)
			balance(node);
		++count;

	}
	void remove(K k)
	{
		auto temp = search(k);
		auto ptemp = temp->parent;
		if (temp->key != k)
		{
			cout << "the key does not exist" << endl;
			return;
		}
		if (hasLchild(temp) && hasRchild(temp))
		{
			remove_dchild(temp);
		}
		else if (hasRchild(temp) && !hasLchild(temp))
		{
			remove_right(temp);
		}
		else if (!hasRchild(temp) && hasLchild(temp))
		{
			remove_left(temp);
		}
		else
		{
			remove_leaf(temp);
		}
		if (ptemp!=nullptr)
			balance(ptemp);
		--count;
	}
	pointer find_non_bal(pointer node)
	{
		pointer ltemp = node->lchild;
		pointer rtemp = node->rchild;
		while (true)
		{
			
			if (ltemp == nullptr && rtemp != nullptr)
			{
				if (rtemp->height >= 1)
					return node;
			}
			else if (ltemp != nullptr && rtemp == nullptr)
			{
				if (ltemp->height >= 1)
					return node;
			}
			else if (ltemp != nullptr && rtemp != nullptr)
			{
				if (abs((ltemp->height) - (rtemp->height)) > bf)
					return node;
			}
		
			if (node == root)
				return nullptr;
			node = node->parent;
			ltemp = node->lchild;
			rtemp = node->rchild;
		}
	}
	void balance(pointer node)
	{
		pointer gp=find_non_bal(node);
		if (gp == nullptr)
			return;
		pointer fp = nullptr;
		pointer vp = nullptr;
		bool pre = false;
		bool after = false;
	
		if (((gp->lchild)) ==max_height(gp->lchild,gp->rchild))
		{
			fp = gp->lchild;
			pre = true;
		}
		else
		{
			fp = gp->rchild;
		}

		if (((fp->lchild)) == max_height(fp->lchild, fp->rchild))
		{
			vp = fp->lchild;
			after = true;
		}
		else
		{
			vp = fp->rchild;
		}

		//if (pre == false && after == false)
		//{
		//	zag(gp, fp);
		//}
		//else if (pre == true && after == true)
		//{
		//	zig(gp, fp);
		//}
		//else if (pre == false && after == true)
		//{
		//	zig(fp, vp);
		//	zag(gp, vp);
		//}
		//else if (pre == true && after == false)
		//{
		//	zag(fp, vp);
		//	zig(gp, vp);
		//}

		if (pre == false && after == false)
		{
			if (gp == root)
			{
				connect34(gp,fp,vp,gp->lchild,fp->lchild,vp->lchild,vp->rchild);
				fp->parent = nullptr;
				root = fp;
				fp->depth = 0;				
			}
			else
			{
				auto pgp = gp->parent;
				connect34(gp, fp, vp, gp->lchild, fp->lchild, vp->lchild, vp->rchild);
				fp->parent = pgp;
				if (pgp->rchild == gp)
				{
					pgp->rchild = fp;
				}
				else
				{
					pgp->lchild = fp;
				}
			}
			fp->depthBelow();
			fp->heightAbove();
		}
		else if (pre == true && after == true)
		{
			if (gp == root)
			{
				connect34(vp, fp, gp, vp->lchild, vp->rchild, fp->rchild, gp->rchild);
				fp->parent = nullptr;
				root = fp;
				fp->depth = 0;
			}
			else
			{
				auto pgp = gp->parent;
				connect34(vp, fp, gp, vp->lchild, vp->rchild, fp->rchild, gp->rchild);
				fp->parent = pgp;
				if (pgp->rchild == gp)
				{
					pgp->rchild = fp;
				}
				else
				{
					pgp->lchild = fp;
				}
			}
			fp->depthBelow();
			fp->heightAbove();
		}
		else if (pre == false && after == true)
		{
			if (gp == root)
			{
				connect34(gp, vp, fp, gp->lchild, vp->lchild, vp->rchild, fp->rchild);
				vp->parent = nullptr;
				root = vp;
				vp->depth = 0;
			}
			else
			{
				auto pgp = gp->parent;
				connect34(gp, vp, fp, gp->lchild, vp->lchild, vp->rchild, fp->rchild);
				vp->parent = pgp;
				if (pgp->rchild == gp)
				{
					pgp->rchild = vp;
				}
				else
				{
					pgp->lchild = vp;
				}
			}
			vp->depthBelow();
			vp->heightAbove();
		}
		else if (pre == true && after == false)
		{
			if (gp == root)
			{
				connect34(fp, vp, gp, fp->lchild, vp->lchild, vp->rchild, gp->rchild);
				vp->parent = nullptr;
				root = vp;
				vp->depth = 0;
			}
			else
			{
				auto pgp = gp->parent;
				connect34(fp, vp, gp, fp->lchild, vp->lchild, vp->rchild, gp->rchild);
				vp->parent = pgp;
				if (pgp->rchild == gp)
				{
					pgp->rchild = vp;
				}
				else
				{
					pgp->lchild = vp;
				}
			}
			vp->depthBelow();
			vp->heightAbove();
		}
		
	}
	void connect34(pointer a, pointer b, pointer c, pointer T0, pointer T1, pointer T2, pointer T3)
	{
		a->lchild = T0;
		if (T0 != nullptr)
		{
			T0->parent = a;
		}
		a->rchild = T1;
		if (T1 != nullptr)
		{
			T1->parent = a;
		}

		c->lchild = T2;
		if (T2 != nullptr)
		{
			T2->parent = c;
		}
		c->rchild = T3;
		if (T3 != nullptr)
		{
			T3->parent = c;
		}

		b->lchild = a;a->parent = b;
		b->rchild = c;c->parent = b;
		
		

		a->heightUpdate();
		c->heightUpdate();
		b->heightUpdate();
	}
	void zig(pointer& pre, pointer& aft)
	{
		pointer temp = nullptr;
		if (aft->rchild != nullptr)
		{
			temp = aft->rchild;
			temp->parent = pre;
			pre->lchild = temp;
		}

		aft->parent = pre->parent;
		pre->parent = aft;
		if (aft->parent == nullptr)
			root = aft;
		else if ((aft->parent)->lchild == pre)
			(aft->parent)->lchild = aft;
		else if ((aft->parent)->rchild == pre)
			(aft->parent)->rchild = aft;
		aft->rchild = pre;
		pre->lchild = temp;
		if (aft->parent != nullptr)
			(aft->parent)->depthBelow();
		else
		{
			aft->depth = 0;
			aft->depthBelow();
		}
		pre->heightAbove();
	}
	void zag(pointer& pre, pointer& aft)
	{
		pointer temp = nullptr;
		if (aft->lchild != nullptr)
		{
			temp = aft->lchild;
			temp->parent = pre;

		}
		aft->parent = pre->parent;
		pre->parent = aft;
		if (aft->parent == nullptr)
			root = aft;
		else if ((aft->parent)->lchild == pre)
			(aft->parent)->lchild = aft;
		else if ((aft->parent)->rchild == pre)
			(aft->parent)->rchild = aft;
		aft->lchild = pre;
		pre->rchild = temp;
		if (aft->parent != nullptr)
			(aft->parent)->depthBelow();
		else
		{
			aft->depth = 0;
			aft->depthBelow();
		}
		pre->heightAbove();
	}

	pointer max_height(pointer a, pointer b)
	{
		if (a == nullptr && b == nullptr)
			return nullptr;
		else if (a == nullptr && b != nullptr)
			return b;
		else if (a != nullptr && b == nullptr)
			return a;
		else
		{
			if (a->height > b->height)
				return a;
			else
				return b;
		}
	}
	iterator begin()
	{
		pointer temp = findMin(root);
		return iterator(temp);
	}
	iterator end()
	{
		pointer temp = findMax(root);
		return iterator(temp->rchild);
	}
	void show2()
	{
		auto index = findMin(root);
		for (auto temp = 0; temp < count; ++temp)
		{
			cout << index->key << "--" << index->height << "--" << index->depth << endl;
			index = index->next();
		}
	}
	void show()
	{
		auto ss = end();
		for (auto temp = begin(); temp != end(); ++temp)
		{
			cout << (*temp).key << "----" << (*temp).value << endl;

		}

	}
};
#endif